/*
 * @lc app=leetcode.cn id=19 lang=java
 *
 * [19] 删除链表的倒数第 N 个结点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 1. 创建一个虚拟头结点
        ListNode dummy = new ListNode(0, head);

        // 2. 创建两个指针，分别指向虚拟头结点
        ListNode first = dummy;
        ListNode second = dummy;

        // 3. 第一个指针先走n+1步
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }

        // 4. 两个指针同时走，直到第一个指针走到最后一个结点
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // 5. 删除第二个指针指向的结点
        second.next = second.next.next;

        return dummy.next;



    }
}
// @lc code=end

